package offer2

/*
*
原题链接：
https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/

B站 吴师兄学算法
剑指 Offer 63. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:
输入: [7,1,5,3,6,4]
输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
*/
func maxProfit(prices []int) int {
	//1.如果股票数组长度<2, 只能当前买卖, 返回利润0即可
	if len(prices) < 2 {
		return 0
	}

	//2.创建dp数组
	dp := make([]int, len(prices))
	//3.声明dp[0]=0, 第一天的最大利润只能是0
	dp[0] = 0
	//4.当前买入价格为prices[0]
	buy := prices[0]

	//5.遍历股票数组
	for i := 1; i < len(prices); i++ {
		//5.1当前的股票价格
		sell := prices[i]
		//5.2当天能够获取的利润
		profit := sell - buy
		//5.3 dp[i] = max(当天利润, dp[i-1])
		dp[i] = max(dp[i-1], profit)

		//5.4 更新buy买入的最小值
		buy = min(buy, prices[i])
	}

	//6.返回dp[len(prices)-1]
	return dp[len(prices)-1]
}
